package leetcode.每日一题;

import org.junit.Test;

import java.util.ArrayList;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/16 15:16
 * @description :https://leetcode-cn.com/problems/beautiful-arrangement/
 */
public class 优美的排列 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.countArrangement(15));
    }

    class Solution {
        int ans = 0;
        public int countArrangement(int n) {
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                list.add(i + 1);
            }
            dfs(1, list);
            return ans;
        }

        private void dfs(int i, ArrayList<Integer> list) {
            if (list.size() == 0) {
                ans++;
                return;
            }
            for (int j = 0; j < list.size(); j++) {
                ArrayList<Integer> sub = new ArrayList<>(list);
                int cur = list.get(j);
                if (cur % i == 0 || i % cur == 0) {
                    sub.remove(j);
                    dfs(i + 1, sub);
                }
            }
        }
    }


}
